package org.shj.algorithm.dhsjjg.tree;

public class BiSortTree {

	private int data;
	
	private BiSortTree leftTree;
	
	private BiSortTree rightTree;
	
	private BiSortTree parent;
	
	public void init(int[] datas){
		data = datas[0];
		
		for(int i = 1 ; i < datas.length ; i++){
			insert(this, datas[i]);
		}
	}
	
	public void insert(BiSortTree tree, int d){
		if(d > tree.getData()){
			if(tree.getRightTree() == null){
				BiSortTree right = new BiSortTree();
				right.setData(d);
				tree.setRightTree(right);
				right.setParent(tree);
			}else{
				insert(tree.getRightTree(), d);
			}
		}else{
			if(tree.getLeftTree() == null){
				BiSortTree left = new BiSortTree();
				left.setData(d);
				tree.setLeftTree(left);
				left.setParent(tree);
			}else{
				insert(tree.getLeftTree(), d);
			}
		}
	}
	
	public void deleteNode(BiSortTree tree, int key){
		if(key > tree.getData()){
			deleteNode(tree.getRightTree(), key);
		}else if(key == tree.getData()){
			deleteNode(tree);
		}else{
			deleteNode(tree.getLeftTree(), key);
		}
	}
	
	private void deleteNode(BiSortTree tree){
		if(tree.getLeftTree() == null && tree.getRightTree() == null){//
			if(tree.getParent().getLeftTree() == tree){
				tree.getParent().setLeftTree(null);
			}else{
				tree.getParent().setRightTree(null);
			}
		}else if(tree.getLeftTree() != null && tree.getRightTree() == null){
			if(tree.getParent().getLeftTree() == tree){
				tree.getParent().setLeftTree(tree.getLeftTree());
			}else{
				tree.getParent().setRightTree(tree.getLeftTree());
			}
		}else if(tree.getRightTree() != null && tree.getLeftTree() == null){
			if(tree.getParent().getLeftTree() == tree){
				tree.getParent().setLeftTree(tree.getRightTree());
			}else{
				tree.getParent().setRightTree(tree.getRightTree());
			}
		}else{
			BiSortTree left = tree.getLeftTree();//删除的结点的左孩子树
			BiSortTree max = left.getRightTree();
			while(max.getRightTree() != null){//得到左孩子树中最大值
				max = max.getRightTree();
			}
			
			if(tree.getParent().getLeftTree() == tree){
				tree.getParent().setLeftTree(max);
			}else{
				tree.getParent().setRightTree(max);
			}
			max.setLeftTree(tree.getLeftTree());
			max.setRightTree(tree.getRightTree());
			
			if(tree.getRightTree() != null){
				tree.getRightTree().setParent(max);
			}
			if(tree.getLeftTree() != null){
				tree.getLeftTree().setParent(max);
			}
			
			max.getParent().setRightTree(null);
			max.setParent(tree.getParent());
		}
	}
	
	public void midOrder(BiSortTree tree){
		if(tree == null){
			return;
		}
		midOrder(tree.getLeftTree());
		System.out.print(tree.getData() + " ");
		midOrder(tree.getRightTree());
	}
	
	
	public static void main(String[] args){
		BiSortTree tree = new BiSortTree();
		tree.init(new int[]{62, 88, 58, 47, 35, 73, 51, 99, 37, 93});
		
		tree.midOrder(tree);
		
		System.out.println();
		tree.deleteNode(tree, 99);
		tree.midOrder(tree);
		
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public BiSortTree getLeftTree() {
		return leftTree;
	}

	public void setLeftTree(BiSortTree leftTree) {
		this.leftTree = leftTree;
	}

	public BiSortTree getRightTree() {
		return rightTree;
	}

	public void setRightTree(BiSortTree rightTree) {
		this.rightTree = rightTree;
	}

	public BiSortTree getParent() {
		return parent;
	}

	public void setParent(BiSortTree parent) {
		this.parent = parent;
	}
	
	
}
